package com.algorithm.array;

/**
 * Created by dongxie on 2021/12/8.
 * https://leetcode-cn.com/problems/remove-element/
 */
public class RemoveElement {
    public static void main(String[] args) {

    }

    /**
     * 暴力解法
     * 这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
     * // 时间复杂度：O(n^2)
     * // 空间复杂度：O(1)
     * @param nums
     * @param target
     * @return
     */
    public int removeElement1(int[] nums, int target) {
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            if (nums[i] == target) { // 发现需要移除的元素，就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--;// 因为下表i以后的数值都向前移动了一位，所以i也向前移动一位
                size--;// 此时数组的大小-1
            }
        }
        return size;
    }

    /**
     * 双指针法
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     *
     * @param nums
     * @param target
     * @return
     */
    public int removeElement2(int[] nums, int target) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != target) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
}
